package com.ds.bintree.NewCoder;

import java.util.LinkedList;
import java.util.List;

/**
 * @author Dianzhi Han
 * @version 1.0
 * @description: 二叉搜索树转为双向链表
 * @date 2022/9/14 18:16
 */
public class JZ36_BST2LinkedList {
    List<TreeNode> list = new LinkedList<>();
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree==null){
            return null;
        }
        inorder(pRootOfTree);


        //修改左右子树的指向
        for(int i = 0;i<list.size()-1;i++){
            list.get(i).right = list.get(i+1);//get最后一个不知道会不会为null
        }
        list.get(list.size()-1).right = null;
        for (int i = list.size()-1; i >0 ; i--) {
            list.get(i).left = list.get(i-1);
        }
        list.get(0).left = null;
        return list.get(0);
    }


    /**
     * 中序遍历
     * @param root
     */
    public void inorder(TreeNode root){
        if (root==null){
            return;
        }
        inorder(root.left);
        list.add(root);
        inorder(root.right);
    }
}
